package ExchangeSort;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 27
 *@time:      18:00
 *
 */

//快速排序
//中心思想：是Hoare于1962年提出的一种二叉树结构的交换排序方法
// 任取待排序元素序列中的某元素作为基准值，
// 按照该排序码将待排序集合分割成两子序列，
// 左子序列中所有元素均小于基准值，
// 右子序列中所有元素均大于基准值，
// 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
import javax.print.DocFlavor;
import java.util.Arrays;
import java.util.Stack;

/*
 * 时间复杂度：O(N*logN) - 好情况        O(N^2) 有序或者逆序 - 坏情况
 * 空间复杂度：O(log(2)N) - 好情况       O(N) - 坏情况
 * 稳定性；不稳定
 * */
public class QuickSort {

    //非递归实现快速排序
    public static void quickSort(int[] arr) {
       Stack<Integer> stack = new Stack<>();
       int start = 0;
       int end = arr.length - 1;

       /*//-----优化
       if (end - start + 1 <= 20) {
           insertSort1(arr, start, end);
           return ;
       }
       int mid = threeNum(arr,start,end);
       swap(arr,mid,start);
       //-----*/

       int pivot = parttion(arr,start,end);
        // 基准 左边的元素要大于2个
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot-1);
        }
        // 基准 右边的元素要大于2个
        if (pivot < end - 1) {
            stack.push(pivot+1);
            stack.push(end);
        }

        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            /*//------ 优化
            if (end - start + 1<= 20) {
                insertSort1(arr,start,end);
            }else {
                //三数取中法
                mid = threeNum(arr, start, end);
                //交换
                swap(arr, mid, start);
            //------*/


                pivot = partition(arr, start, end);

                // 基准 左边的元素要大于2个
                if (pivot > start + 1) {
                    stack.push(start);
                    stack.push(pivot-1);
                }
                // 基准 右边的元素要大于2个
                if (pivot < end - 1) {
                    stack.push(pivot+1);
                    stack.push(end);
                }
            }

        }
    //}

    public static void quickSort1(int[] arr) {
        quick(arr, 0, arr.length-1);
    }


    //三树取中法 -- 快排的优化
/* 中心思想：
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
*/
    private static int threeNum(int[] arr, int left, int right) {
        //定义一个中间值 -- 要返回这个中间值 与 原先的基准交换
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) {
                return left;
            }else if (arr[mid] > arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {//arr[left] > arr[right]
            if (arr[mid] > arr[left]) {
                return left;
            }else if (arr[mid] < arr[right]){
                return right;
            }else {
                return mid;
            }
        }
    }

    private static void insertSort1(int[] arr, int left, int right) {
        for (int i = left+1; i < right; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }

    }

    public static void quick(int[] arr, int start, int end) {
        //结束条件
        if (start >= end) {
            return;
        }
        //因为 越有序 直接插入排序越快 -- 此处可以引入直接插入排序
        if (end - start <= 20) {
            //此处是 排序 排某一段
            insertSort1(arr, start, end);
            return;
        }

        //三数取中法
        int mid = threeNum(arr, start, end);
        //交换
        swap(arr, mid, start);


        //基准
        int pivot = parttion(arr,start,end);
        //左树
        quick(arr,start, pivot-1);
        //右树
        quick(arr,pivot+1,end);
    }

    // Hoare法
    private static int parttion1(int[] arr, int left, int right) {
        int i = left;//记录首元素地址位置
        int tmp = arr[left];//基准
        while (left < right) {
            //从右边 找到比基准大的
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            //从左边找到比基准小的
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            //交换 - 使得基准右边的值都大于左边
            swap(arr,left, right);
        }
        //更换基准
        swap(arr,left,i);
        //返回更换后的基准
        return left;
    }

    //挖坑法
    private static int parttion(int[] arr, int left, int right) {
        int i = left;//记录首元素地址位置
        int tmp = arr[left];//基准
        while (left < right) {
            //从右边 找到比基准大的
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            // 填坑
            arr[left] = arr[right];
            //从左边找到比基准小的
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            // 填坑
            arr[right] = arr[left];
            //交换 - 使得基准右边的值都大于左边
            swap(arr,left, right);
        }
        // 填相遇地方的坑
        arr[left] = tmp;
        //返回更换后的基准
        return left;
    }

    //前后指针法 - way1
    private static int partition(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //前后指针法 - way2
    private static int partition2(int[] array, int left, int right) {
        int d = left + 1;
        int pivot = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                swap(array, i, d);
                d++;
            }
        }
        swap(array, d - 1, left);
        return d - 1;
    }

    private static void swap(int[] arr, int i , int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr1 = {2,8,7,3,9,5,9,0,0,2};
        int[] arr = {10,2,8,7,3,9,5,9,0,0,2};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
